1. Field of the Invention
This invention relates generally to data packet routing procedures in multinode networks and more particularly to an adaptive path discovery and reconfiguration procedure for distributed networks.
2. Description of the Related Art
A network includes a plurality of data packet switches (denominated “routers”) interconnected with suitable technology such as point-to-point links, data packet repeaters (transparent bridges) or local area networks (LANs). The purpose of a network is to enable users who attach their equipment (denominated “endnodes”) to the network to transmit data to and receive data from the other users' endnode equipment. As shown in FIG. 1, to the endnode 20, the network 22 is merely a large “cloud” to which it attaches, thereby enabling itself to communicate with other endnodes such as the endnodes 24 and 26 that are also attached to the cloud 22 over the plurality of links composing the network topology and exemplified by the links 28 and 30 that form part of the path 32 between endnode 20 (source) and endnode 26 (destination) in FIG. 1. Endnodes, bridges and routers are herein also generally denominated “nodes.”
The Open Systems Interconnection (OSI) Reference Model defines seven network protocol layers. According to the OSI Reference Model, each layer within a node communicates with its peer layers in foreign nodes by exchanging protocol data units (PDUs) across the network. To effect such PDU transfers, each layer makes use of the services available from the lower layer in its node by exchanging service data units (SDUs) with its local adjacent layer.
The physical layer (layer 1) transmits bits of information across a link and deals with such problems as connector size and shape, assignment of connector pin functions, conversion of bits to electrical or optical signals, and bit-level synchronization. There may be several different types of physical layers within a network and even several different types of physical layers within a single node because each physical technology (e.g., CMOS, infrared, fiber optics, et al.) requires its own physical layer.
The data link layer (layer 2) transmits chunks of information across a link. Different links may implement different data link layers and a single node may support several data link layer protocols. The data link layer uses the services of the physical layer to transmit link PDUs (LPDUs) to its peer data link layer in another node of the network. The “transparent bridge” operates in the data link layer.
The network layer (layer 3) enables any pair of nodes in a network to communicate with one another. A “fully connected” network is one in which every pair of nodes is connected by a direct link, but such a topology does not scale beyond a few nodes because of the exponential increase in link numbers. More typically, in a distributed multinode network, the network layer must find a path through a series of interconnected nodes, each of which must forward data packets in the appropriate direction. The network layer deals with such problems as path calculation, packet fragmentation and reassembly (to handle maximum packet size variation from link to link), and congestion control. The network layer uses the services of the data link layer to transmit network PDUs (NPDUs) to its peer network layer in another node of the network. The data packet switch (router) operates in the network layer.
When an endnode wants to send data to a remote node across the network, the sending endnode (source) must know the address of the destination node and must also know at least the first link in the path (route) from source to destination. Many routing strategies are known in the art but no one strategy is better than all others according to all measures of goodness. The “source routing” protocol is well known in the art. The basic idea behind source routing is that each packet header contains a path specification that was inserted into the packet by the source node itself. For the source node to have a path to the destination node available for insertion into a packet, it must first discover the path by some means. The source routing standard embraces many methods that can be used by a source node to establish and maintain paths. With strict source routing, the entire list of intermediate nodes is specified in a packet route list. With loose source routing, the packet route list may specify only a few intermediate addresses along the path that the packet must not miss visiting in a specified sequence during its journey through the network. The basic idea behind strict source routing is that a source endnode keeps a cache of routes for destination nodes with which it is currently having conversations. If no path for a particular destination is in the cache, the source node can employ a “path discovery” protocol to find a path or a set of paths. If a path in the cache is found to no longer work, the source can either attempt to find another new path or use one of the alternate routes it has stored for the destination.
In networks using bridges, the source node may discover a path by transmitting a special kind of data packet (an “explorer” packet) that replicates itself as it encounters branches or choices en route, eventually sending an explorer packet copy over each possible path in the network. Each explorer packet copy collects the diary of its travels so that a path can be selected from among the many explorer packet copies that reach the destination node and returned in a message to the source node. Whenever a source node discovers a path to another node, it caches the path so that it can be used for subsequent packets to the same destination. The problem of exponential explorer packet proliferation may be reduced by using the spanning tree explorer packet process known in the art. However, all source routing bridges must execute a spanning tree algorithm to support the spanning tree explorer packet process, which may be burdensome. As multiple explorer packets arrive at a destination node, one of the several available paths must be selected according to some strategy. Exemplary strategies include selecting the first packet received (on the theory that it travels on the fastest path); selecting the path that indicates maximum packet size; selecting the pathwith the fewest hops; selecting the most recently received path; or selecting some combination of the preceding.
Network layer routing protocols known in the art are based on either the “distance vector” or the “link state” distributed routing procedures. Distance vector routing requires that each node maintain the distance (a measure of transit cost) from itself to each possible destination. The distances making up a local distance vector are recursively computed within the local node by assembling and using the information from the distance vectors found at neighboring nodes. The chief problem with distance vector routing is the slow convergence of the distance vectors across the network. When routing information has only partially propagated through a network, routing performance can be seriously disrupted. Because a single link change may affect many paths, it is important for routing to recover as quickly as possible after a topological change in the network. Distance vector routing can take a very long time to converge after such a topological change. Practitioners have proposed numerous solutions to the slow convergence problem in distance vector routing, including the diff-using update algorithm (DUAL), the “split horizon” technique, the “fall path reporting” technique, the “poison reverse” technique, the “triggered-update” technique and various “hold-down” techniques. Unfortunately, none of these proposals has eliminated the basic disadvantages of the distance vector routing procedures. The primary advantage is that it requires less node memory than the link state routing procedures.
The link state routing procedure implements the basic idea that each router is responsible for meeting its neighbors and learning their names. Each router constructs a special packet (a link state packet or LSP) that contains a list of the names of and the cost (distance) to each of its adjacent neighbor nodes. The LSP is somehow transmitted to all other nodes and each node stores the most recently generated LSP from each and every other node in the network. Each node may then compute routes to any destination based on the complete map of the network topology derived from the accumulated LSP information. Link state routing is subject to many serious well-known problems such as “cancerous” LSP distribution and LSP incompatibility among nodes; conditions arising from ineffective transmission of a new LSP to all other nodes in the network when the local link states change. Other disadvantages known in the art include the drastic difficulties arising from time-stamp synchronization failure and sequence-number wrap-around. Moreover, either the link state routing or the distance vector routing procedure can be completely disabled by a single rogue router (denominated a “Byzantine” failure), although at least one link state routing protocol in the art has been proven to be immune to Byzantine failures (by Radia Perlman). Despite the large operational overhead, link state routing is preferred in the art mainly because of the faster network convergence on topology changes.
The art is replete with proposals for improving the path discovery and maintenance process in multinode networks. For example, Shin et al. [Kang G. Shin et al., “Distributed Route Selection for Establishing Real-Time Channels,” IEEE Trans. Parallel and Distributed Systems, vol. 11, no. 2, pp. 318–335, Mar. 2000] propose an improved link state routing procedure that eases the centralized route selection bottleneck while improving efficiency by quickly pruning infeasible routes from the parallel route search. Shin et al. are primarily concerned with “completeness” (ensuring the discovery of a qualified route if one exists) and use a modified Bellman-Ford algorithm that is less efficient than the original, but neither consider nor suggest solutions to the problem of adaptively discovering a path between network endnodes in a dynamic network topology. Another proposal for improved link state routing efficiency in Private Network to Network Interface (PNNI) Based Asynchronous Transfer Mode (ATM) networks is the modified Dijkstra path optimization algorithm disclosed by Rochberger et al. in U.S. Pat. No. 6,147,971. The Dijkstra procedure is a link-state routing protocol that uses intensive node processing to minimize the “cost” of a path and the Rochberger et al. proposal improves the convergence time of the Dijkstra protocol for hop-count minimization only.
In U.S. Pat. No. 6,047,330, Stracke, Jr., proposes a virtual router discovery system for building a multicast virtual network over an existing topology and for dynamically adapting the routing system responsively to unpredicted changes in underlying network connectivity. Stracke, Jr., use virtual routers that send out “heartbeats” across the Internet Protocol (IP) network, each marked with a Time To Live (TTL) value. Each router returns a response packet upon receiving the heartbeat packet and the originating router obtains an estimate of the distance (cost) to the responding router upon receipt of the response packet. By selecting closer routers with which to connect, the system automatically and dynamically adapts to network changes by dropping inefficient connections in favor of more efficient ones. But Stracke, Jr., neither considers nor suggests solutions to the problem of discovering a path between network endnodes in a dynamic network topology.
In U.S. Pat. No. 6,023,733, Periasamy et al. disclose an efficient method for representing a link state table in a node, thereby permitting storage of a representation of the entire network at each node with less memory demand. But they neither consider nor suggest solutions to the dynamic path discovery problem.
In U.S. Pat. No. 6,201,794, Stewart et al. disclose a dynamic path discovery technique intended to determine the most efficient path for transmitting a message from a source node to many other destination nodes considering prevailing network traffic conditions. Pilot messages are transmitted between communicating nodes either periodically or continuously to monitor the “cost” of each available path. The various paths traversed by pilot messages are returned to the originating node and stored for use in selecting the most efficient (least cost) path. A master riding node can alter pilot message sequencing responsively to network traffic conditions to more frequently update path analysis over busy routes. Disadvantageously, this technique tends to increase network message traffic over the busier routes.
There still exists a well-known need for a path selection system which can dynamically adapt to changes in network connectivity and traffic conditions without adding significantly to network traffic congestion and node operational overhead. The related unresolved problems and deficiencies are clearly felt in the art and are solved by this invention in the manner described below.